/*
 * @Author: guojiangang guojiangang@hikvision.com.cn
 * @Date: 2024-02-28 10:08:54
 * @LastEditors: guojiangang guojiangang@hikvision.com.cn
 * @LastEditTime: 2024-02-28 10:41:35
 * @FilePath: \cfase:\leetcode\169.多数元素.js
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=169 lang=javascript
 *
 * [169] 多数元素
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  // 因为大于一半, 所以排序后的 中间那个数必是
  nums.sort((a,b) => a - b)
  return nums[Math.floor(nums.length / 2)]
};

// 用对象记录数出现的次数, 大于一半的就是了
var majorityElement = function(nums) {
  const map = {}
  const hn = nums.length / 2
  for (const n of nums) {
    map[n] = (map[n] || 0) + 1
    if (map[n] > hn) return n
  }
};

// 抵消(栈方法降维)
// 相同的加1, 不相同的减1, 因为是大于一半, 所以最后肯定剩下大于一半的那个
// var majorityElement = function(nums) {
//   let x = 0;
//   let m = 0
//   for (const n of nums) {
//     if (m === 0) x = n
//     m += x === n ? 1 : -1
//   }
//   return x
// }
// @lc code=end

